{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Increment to Make Array Unique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #counting #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #计数 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minIncrementForUnique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使数组唯一的最小增量"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 。每次 move 操作将会选择任意一个满足 <code>0 &lt;= i &lt; nums.length</code> 的下标 <code>i</code>，并将&nbsp;<code>nums[i]</code> 递增&nbsp;<code>1</code>。</p>\n",
    "\n",
    "<p>返回使 <code>nums</code> 中的每个值都变成唯一的所需要的最少操作次数。</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,2]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>经过一次 <em>move</em> 操作，数组将变为 [1, 2, 3]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,2,1,2,1,7]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>经过 6 次 <em>move</em> 操作，数组将变为 [3, 4, 1, 2, 5, 7]。\n",
    "可以看出 5 次或 5 次以下的 <em>move</em> 操作是不能让数组的每个值唯一的。</pre>\n",
    "</div>\n",
    "</div>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "<strong>提示：</strong>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-increment-to-make-array-unique](https://leetcode.cn/problems/minimum-increment-to-make-array-unique/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-increment-to-make-array-unique](https://leetcode.cn/problems/minimum-increment-to-make-array-unique/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,2]', '[3,2,1,2,1,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        mid = []\n",
    "        mid.append([nums[0], nums[0]])\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == mid[-1][1] + 1:\n",
    "                mid[-1][1] += 1\n",
    "            elif nums[i] <= mid[-1][1]:\n",
    "                count += mid[-1][1] - nums[i] + 1\n",
    "                mid[-1][1] += 1\n",
    "            else:\n",
    "                mid.append([nums[i], nums[i]])\n",
    "        return count\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        for i in range(n-1,0,-1):\n",
    "            if nums[i] == nums[i-1]:##存在重复的情况\n",
    "                flag = True\n",
    "                while flag:\n",
    "                    nums[i] += 1\n",
    "                    count += 1\n",
    "                    if nums[i] not in nums[(i+1):]:\n",
    "                        flag = False\n",
    "        return count\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import *\n",
    "class Solution:\n",
    "    def minIncrementForUnique0(self, nums: List[int]) -> int:\n",
    "        # 计数排序，每次遇到大于1的数只保留1个，剩下的往后移\n",
    "        # 最大值的右边可能会堆积，需要对最大值右侧进行操作，如果x积累d个，后面的数\n",
    "        # 应该为[x+1,x+2, x+3, ...., x+d]，求和公式\n",
    "        pass\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans, n = 0, len(nums)\n",
    "        for i in range(1, n):\n",
    "            if nums[i] <= nums[i-1]:\n",
    "                ans += nums[i-1] + 1 - nums[i] # 每遇到当前元素小于等于前一个元素，将当前元素变为前一个元素+1，并记录差值\n",
    "                nums[i] = nums[i-1] + 1\n",
    "        return ans\n",
    "        \n",
    "    def minIncrementForUnique2(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        sortDict = SortedDict(int)\n",
    "        c = Counter(nums)\n",
    "        for k,v in c.items():\n",
    "            sortDict[k] = v\n",
    "        while True:\n",
    "            duplicateFlag = False\n",
    "            for digit, count in sortDict.items():\n",
    "                if count > 1:\n",
    "                    sortDict[digit] -= 1\n",
    "                    if digit+1 in sortDict:\n",
    "                        sortDict[digit+1] += 1\n",
    "                    else:\n",
    "                        sortDict[digit+1] = 1\n",
    "                    ans += 1\n",
    "                if sortDict[digit] > 1:\n",
    "                    duplicateFlag = True\n",
    "            if not duplicateFlag:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        ans=0\n",
    "        for i in range(1,n):\n",
    "            if nums[i]<=nums[i-1]:\n",
    "                ans+=nums[i-1]-nums[i]+1\n",
    "                nums[i]=nums[i-1]+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, A: List[int]) -> int:\n",
    "        A.sort()\n",
    "        count = 0\n",
    "        for i in range(1, len(A)):\n",
    "            if A[i-1] >= A[i]:\n",
    "                count += A[i-1]+1-A[i]\n",
    "                A[i] = A[i-1]+1\n",
    "        return count\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, A: List[int]) -> int:    \n",
    "\n",
    "        A.sort()\n",
    "        res= 0\n",
    "        for i in range(1, len(A)):\n",
    "            if A[i]<=A[i-1]:\n",
    "                res+= A[i-1]-A[i]+1\n",
    "                A[i]=A[i-1]+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        nums.append(float('inf'))\n",
    "        pre = nums[0]\n",
    "        for i in range(1, n):\n",
    "            curr = nums[i]\n",
    "            post = max(curr, pre + 1)\n",
    "            pre = post\n",
    "            ans += post - curr\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        i, ans = 0, 0\n",
    "        for a in sorted(nums):  # 将 A 改为 nums\n",
    "            ans += max(i - a, 0)\n",
    "            i = max(a, i) + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        i, ans = 0, 0\n",
    "        for a in sorted(nums):  # 将 A 改为 nums\n",
    "            ans += max(i - a, 0)\n",
    "            i = max(a, i) + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        count = 0\n",
    "        print(nums)\n",
    "        mid = []\n",
    "        mid.append([nums[0], nums[0]])\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == mid[-1][1] + 1:\n",
    "                mid[-1][1] += 1\n",
    "            elif nums[i] <= mid[-1][1]:\n",
    "                count += mid[-1][1] - nums[i] + 1\n",
    "                mid[-1][1] += 1\n",
    "            else:\n",
    "                mid.append([nums[i], nums[i]])\n",
    "            #print(\"%d\\t%s\" % (nums[i], str(mid)))\n",
    "        \n",
    "        return count\n",
    "\n",
    "\n",
    "        \"\"\"\n",
    "        for i in range(n-1,0,-1):\n",
    "            if nums[i] == nums[i-1]:##存在重复的情况\n",
    "                flag = True\n",
    "                while flag:\n",
    "                    nums[i] += 1\n",
    "                    count += 1\n",
    "                    if nums[i] not in nums[(i+1):]:\n",
    "                        flag = False\n",
    "        return count\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums_obtained = []\n",
    "        move = 0\n",
    "\n",
    "        for num in nums:\n",
    "            if not nums_obtained:\n",
    "                nums_obtained.append(num)\n",
    "            else:\n",
    "                step = max(0, nums_obtained[-1] - num + 1)\n",
    "                move += step\n",
    "                nums_obtained.append(num + step)\n",
    "\n",
    "        return move"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        prev = -1\n",
    "        res = []\n",
    "        for x in nums:\n",
    "            if prev < x:\n",
    "                prev = x\n",
    "                res.append(prev)\n",
    "            else:\n",
    "                res.append(prev + 1)\n",
    "                prev += 1\n",
    "                \n",
    "        return sum(x-y for x, y in zip(res, nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        counter = [0] * 100002\n",
    "        max1 = -1\n",
    "        for num in nums:\n",
    "            counter[num] += 1\n",
    "            max1 = max(max1, num)\n",
    "        mov = 0\n",
    "        num = 0\n",
    "        while num <= max1:\n",
    "            if counter[num] > 1 :\n",
    "                d = counter[num] - 1\n",
    "                mov += d\n",
    "                counter[num + 1] += d\n",
    "            num += 1\n",
    "        d = counter[max1 + 1] - 1\n",
    "        mov += (d + 1) * d // 2\n",
    "        return mov"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        print(nums)\n",
    "        ans = 0\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                temp = nums[i]\n",
    "                nums[i] = nums[i - 1] + 1\n",
    "                ans += nums[i] - temp\n",
    "                # print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    首先对数组 nums 进行排序，这样可以确保后面的元素大于等于前面的元素。\n",
    "    遍历排序后的数组 nums，对于当前元素 nums[i]，如果它小于等于前一个元素 nums[i-1]，则需要将其递增到 nums[i-1]+1，这样可以保证 nums 中的每个值都是唯一的。\n",
    "    统计递增操作的次数，即为最少操作次数。\n",
    "    \"\"\"\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()  # 对数组进行排序\n",
    "        count = 0  # 记录递增操作的次数\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] <= nums[i - 1]:\n",
    "                count += nums[i - 1] - nums[i] + 1  # 将当前元素递增到前一个元素加1\n",
    "                nums[i] = nums[i - 1] + 1  # 改变当前元素，后面的元素需要以当前元素为基准\n",
    "        print(nums)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        Method2:\n",
    "        用一个数组counter统计所有元素的个数 然后遍历counter 如果个数大于1就后移\n",
    "        \"\"\"\n",
    "        counter = [0 for _ in range(10**5+2)] #最大值+1\n",
    "        max_ = -1 #为了后续遍历不用遍历整个数组\n",
    "        for num in nums:\n",
    "            counter[num] += 1\n",
    "            max_ = max(max_,num)\n",
    "        rs = 0\n",
    "        for num in range(0,max_+1):\n",
    "            if counter[num] > 1:\n",
    "                rs += counter[num]-1 \n",
    "                counter[num+1] += counter[num]-1       \n",
    "        # 最后单独考虑max+1=x 有d个数 那就是要移动到x+1 x+2 x+d 求和公式\n",
    "        d = counter[max_+1]-1\n",
    "        rs += (1+d)*d//2\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        nums_obtained = [nums[0]]\n",
    "        move = 0\n",
    "\n",
    "        for num in nums[1:]:\n",
    "            step = max(0, nums_obtained[-1] - num + 1)\n",
    "            move += step\n",
    "            nums_obtained.append(num + step)\n",
    "\n",
    "        return move"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        if nums == []:\n",
    "            return 0\n",
    "        count = 0\n",
    "        maxn = max(nums)\n",
    "        minn = min(nums)\n",
    "        set1 = set([x for x in range(minn,maxn+len(nums))])\n",
    "        setn = set(nums)\n",
    "        set2 = list(set1-setn)\n",
    "        set2.reverse()\n",
    "        nums.sort()\n",
    "        for i in nums:\n",
    "            if i in setn:\n",
    "                setn.remove(i)\n",
    "                continue\n",
    "            else:\n",
    "                while True:\n",
    "                    if set2[-1] > i:\n",
    "                        count += set2[-1]-i\n",
    "                        set2.pop()\n",
    "                        break\n",
    "                    else:\n",
    "                        set2.pop()\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        n=[0]*500000\n",
    "        l=len(nums)\n",
    "        for i in range(l):\n",
    "            n[nums[i]]+=1\n",
    "        ans=0\n",
    "        for i in range(500000):\n",
    "            if n[i]<=1 :\n",
    "                continue\n",
    "            ans+=n[i]-1\n",
    "            n[i+1]+=n[i]-1\n",
    "            n[i]=1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, A: List[int]) -> int:\n",
    "        def findPos(i):\n",
    "            tryPos = move_dict.get(i, -1)\n",
    "            if tryPos == -1:\n",
    "                pos = i\n",
    "            else:\n",
    "                pos = findPos(tryPos+1)\n",
    "            move_dict[i] = pos\n",
    "            return pos\n",
    "                \n",
    "        move_dict = {}\n",
    "        move = 0\n",
    "        for i in A:\n",
    "            move += findPos(i) - i\n",
    "            \n",
    "        return move"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        print(sorted(nums))\n",
    "        ans=[]\n",
    "        sort_nums=sorted(nums)\n",
    "        for i in range(1,len(sort_nums)):\n",
    "            if sort_nums[i]==sort_nums[i-1]:\n",
    "                sort_nums[i]+=1\n",
    "            if sort_nums[i]<=sort_nums[i-1]:\n",
    "                sort_nums[i]=sort_nums[i-1]+1\n",
    "        print(sort_nums)\n",
    "        nums.sort()\n",
    "        for i in range(len(sort_nums)):\n",
    "            ans.append(sort_nums[i]-nums[i])\n",
    "        return sum(ans)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        length = len(nums)\n",
    "        if length == 1: return 0\n",
    "\n",
    "        # sort nlogn\n",
    "        # nums.sort()\n",
    "        # ans = 0\n",
    "        # for i in range(1, length):\n",
    "        #     if nums[i] > nums[i - 1]: continue\n",
    "        #     else:\n",
    "        #         ans += nums[i - 1] + 1 - nums[i]\n",
    "        #         nums[i] = nums[i - 1] + 1\n",
    "        # return ans\n",
    "\n",
    "        # math\n",
    "        count = [0] * 200001\n",
    "        need = 0\n",
    "        sum_all, max_val = 0, 0\n",
    "        taken = 0\n",
    "        # ans = 0\n",
    "        for num in nums:\n",
    "            count[num] += 1\n",
    "            sum_all += num\n",
    "            max_val = num if num > max_val else max_val\n",
    "\n",
    "        print(sum_all, max_val)\n",
    "        for i in range(200001):\n",
    "            if count[i] == 1:\n",
    "                taken += i\n",
    "                continue\n",
    "            if count[i] > 1:\n",
    "                taken += i\n",
    "                need += count[i] - 1\n",
    "                continue\n",
    "            if need and count[i] == 0:\n",
    "                taken += i \n",
    "                need -= 1\n",
    "                continue\n",
    "            if not need and i >= max_val:\n",
    "                break\n",
    "        \n",
    "        return taken - sum_all\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        count = [0] * 200001\n",
    "        for x in nums:\n",
    "            count[x] += 1\n",
    "        \n",
    "        ans = taken = 0\n",
    "        for x in range(200001):\n",
    "            if count[x] >= 2:\n",
    "                taken += count[x] - 1\n",
    "                ans -= x * (count[x] - 1)\n",
    "            elif taken > 0 and count[x] == 0:\n",
    "                taken -= 1\n",
    "                ans += x\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        # nums.sort()\n",
    "        numdict = [0]*(2*10**5+1)\n",
    "        for i in nums:\n",
    "            numdict[i] += 1\n",
    "        cur = 0\n",
    "        res = 0\n",
    "        for i in range(len(numdict)):\n",
    "            while numdict[i]>1:\n",
    "                while cur<=i or numdict[cur]!=0:\n",
    "                    cur+=1\n",
    "\n",
    "                res+=cur-i\n",
    "                numdict[i]-=1\n",
    "                numdict[cur] = 1\n",
    "        return res\n",
    "                \n",
    "         \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        c = [0] * (10 ** 5 * 2)\n",
    "        for x in nums:\n",
    "            c[x] += 1\n",
    "        ans = taken = 0\n",
    "        for x in range(10 ** 5 * 2):\n",
    "            if c[x] >= 2:\n",
    "                taken += c[x] - 1\n",
    "                ans -= x * (c[x] - 1)\n",
    "            elif taken > 0 and c[x] == 0:\n",
    "                taken -= 1\n",
    "                ans += x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        cnt = [0]*(200001)\n",
    "        for n in nums:\n",
    "            cnt[n] += 1\n",
    "\n",
    "        ans = taken = 0\n",
    "        for i in range(200001):\n",
    "            if cnt[i]>=2:\n",
    "                taken += cnt[i]-1\n",
    "                ans -= i*(cnt[i]-1)\n",
    "            elif taken>0 and cnt[i]==0:\n",
    "                taken -= 1\n",
    "                ans += i  \n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, A: List[int]) -> int:\n",
    "        pos = collections.defaultdict(lambda: -1)\n",
    "        # 线性探测寻址（含路径压缩）\n",
    "        def findpos(a):\n",
    "            if pos[a] == -1:\n",
    "                pos[a] = a\n",
    "                return pos[a]\n",
    "            p = findpos(pos[a] + 1)\n",
    "            pos[a] = p  # 注意要给pos[a]赋值\n",
    "            return pos[a]\n",
    "        \n",
    "        res = 0\n",
    "        for x in A:\n",
    "            p = findpos(x)\n",
    "            res += p - x\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        # print(sorted(nums))\n",
    "        ans=[]\n",
    "        sort_nums=sorted(nums)\n",
    "        for i in range(1,len(sort_nums)):\n",
    "            if sort_nums[i]==sort_nums[i-1]:\n",
    "                sort_nums[i]+=1\n",
    "            if sort_nums[i]<=sort_nums[i-1]:\n",
    "                sort_nums[i]=sort_nums[i-1]+1\n",
    "        # print(sort_nums)\n",
    "        nums.sort()\n",
    "        for i in range(len(sort_nums)):\n",
    "            ans.append(sort_nums[i]-nums[i])\n",
    "        return sum(ans)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "\n",
    "def b_find(ss: SortedSet[int], n: int) -> int:\n",
    "    left, right = 0, len(ss) - 1\n",
    "\n",
    "    while left + 1 < right:\n",
    "        middle = (left + right) // 2\n",
    "\n",
    "        if ss[middle] > n:\n",
    "            right = middle\n",
    "        else:\n",
    "            left = middle\n",
    "\n",
    "    if ss[left] > n:\n",
    "        return ss[left]\n",
    "    if ss[right] > n:\n",
    "        return ss[right]\n",
    "    return ss[right] + 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: list[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        min_n, max_n = min(nums), max(nums) + len(nums)\n",
    "        avaliable = SortedSet(range(min_n, max_n + 1))\n",
    "        ret = 0\n",
    "\n",
    "        for n in nums:\n",
    "            if n in avaliable:\n",
    "                avaliable.remove(n)\n",
    "            else:\n",
    "                a  = b_find(avaliable, n)\n",
    "                ret += a - n\n",
    "                avaliable.remove(a)\n",
    "\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, A: List[int]) -> int:\n",
    "        root = {}\n",
    "        def find(x):\n",
    "            if x not in root:\n",
    "                root[x] = x\n",
    "            elif x != root[x]:\n",
    "                root[x] = find(root[x])\n",
    "            elif x + 1 in root:\n",
    "                root[x] = find(root[x + 1])\n",
    "            else:\n",
    "                root[x] = root[x + 1] = x + 1\n",
    "            return root[x]\n",
    "        return sum(find(a) - a for a in A)\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, A: List[int]) -> int:\n",
    "        root = {}\n",
    "        def find(x):\n",
    "            if x not in root:\n",
    "                root[x] = x\n",
    "            elif x != root[x]:\n",
    "                root[x] = find(root[x])\n",
    "            elif x + 1 in root:\n",
    "                root[x] = find(root[x + 1])\n",
    "            else:\n",
    "                root[x] = root[x + 1] = x + 1\n",
    "            return root[x]\n",
    "        return sum(find(a) - a for a in A)\n",
    "                \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        pos = [-1] * 800000\n",
    "        move = 0\n",
    "        for a in nums:\n",
    "            b = self.findPos(a, pos)\n",
    "            move += b - a\n",
    "        return move\n",
    "\n",
    "    def findPos(self, a, pos):\n",
    "        b = pos[a]\n",
    "        if b == -1:\n",
    "            pos[a] = a\n",
    "            return a\n",
    "        b = self.findPos(b + 1, pos)\n",
    "        pos[a] = b\n",
    "        return b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        cnt=[0]*800000\n",
    "        for n in nums:\n",
    "            cnt[n]+=1\n",
    "\n",
    "        ans=0\n",
    "        flag=0\n",
    "        for i in range(800000):\n",
    "            if cnt[i]>=2:\n",
    "                flag+=cnt[i]-1#记录的是个数\n",
    "                ans-=(cnt[i]-1)*i\n",
    "            elif flag>0 and cnt[i]==0:\n",
    "                flag-=1\n",
    "                ans+=i\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        mset = set()\n",
    "        remains = []\n",
    "        maxV = 0\n",
    "        for v in nums:\n",
    "            if v in mset:\n",
    "                remains.append(v)\n",
    "            else:\n",
    "                mset.add(v)\n",
    "            maxV = max(maxV, v)\n",
    "        maxV = min(maxV+len(nums)+1, 10**5*2)\n",
    "        remains.sort()\n",
    "        remainIdx = 0\n",
    "        rst = 0\n",
    "        for v in range(0, maxV):\n",
    "            if remainIdx == len(remains):\n",
    "                break\n",
    "            if v not in mset and remains[remainIdx] < v:\n",
    "                rst += v - remains[remainIdx]\n",
    "                remainIdx += 1\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        count = [0] * 800000\n",
    "        for x in nums:\n",
    "            count[x] += 1\n",
    "        ans = taken = 0\n",
    "        for x in range(800000):\n",
    "            if count[x] >= 2:\n",
    "                taken += count[x] - 1\n",
    "                ans -= x * (count[x] - 1)\n",
    "            elif taken > 0 and count[x] == 0:\n",
    "                taken -= 1\n",
    "                ans += x\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindRightRange:\n",
    "    # 模板：向右合并的并查集\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if root_x > root_y:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        m = 10**5\n",
    "        uf = UnionFindRightRange(m * 2 + 2)\n",
    "        for num in nums:\n",
    "            # 其根节点就是当前还未被占据的节点\n",
    "            x = uf.find(num)\n",
    "            ans += x - num\n",
    "            uf.union(x, x + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        nums.sort()\n",
    "        s=set()\n",
    "        for i in range(n):\n",
    "            s.add(nums[i])\n",
    "        sum,j=0,nums[0]\n",
    "        for i in range(n):\n",
    "            if i+1<n and nums[i]==nums[i+1]:\n",
    "                if j<nums[i]:\n",
    "                    j=nums[i]\n",
    "                while j in s:\n",
    "                    j+=1\n",
    "                sum+=j-nums[i]\n",
    "                j+=1\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        dic = defaultdict(int)\n",
    "        for i in nums:\n",
    "            dic[i] += 1\n",
    "        t = sorted(dic.keys())\n",
    "        tm = []\n",
    "        for i in range(len(t)):\n",
    "            if dic[t[i]] > 1:\n",
    "                tm.append(t[i])\n",
    "        ans = 0\n",
    "        i = t[0]\n",
    "        while tm!=[]:\n",
    "            if i not in dic and i > tm[0]:\n",
    "                ans += i-tm[0]\n",
    "                dic[tm[0]] -= 1\n",
    "                if dic[tm[0]] == 1:\n",
    "                    tm.pop(0)\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindRightRange:\n",
    "    # 模板：向右合并的并查集\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.root = [i for i in range(n)]\n",
    "        return\n",
    "\n",
    "    def find(self, x):\n",
    "        lst = []\n",
    "        while x != self.root[x]:\n",
    "            lst.append(x)\n",
    "            # 在查询的时候合并到顺带直接根节点\n",
    "            x = self.root[x]\n",
    "        for w in lst:\n",
    "            self.root[w] = x\n",
    "        return x\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x = self.find(x)\n",
    "        root_y = self.find(y)\n",
    "        if root_x == root_y:\n",
    "            return False\n",
    "        if root_x > root_y:\n",
    "            root_x, root_y = root_y, root_x\n",
    "        self.root[root_x] = root_y\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        # 模板：可使用向右合并的区间并查集，正解为贪心\n",
    "        nums.sort()\n",
    "        ans = 0\n",
    "        uf = UnionFindRightRange(max(nums)+len(nums) + 2)\n",
    "        for num in nums:\n",
    "            # 其根节点就是当前还未被占据的节点\n",
    "            x = uf.find(num)\n",
    "            ans += x - num\n",
    "            uf.union(x, x + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        '''\n",
    "        3 2 1 2 1 7\n",
    "        1 1 2 2 3 7\n",
    "        1->4 2->5\n",
    "        '''\n",
    "        n = len(nums)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        next_num = nums[0]\n",
    "        exists = set(nums)\n",
    "\n",
    "        def get_next(num):\n",
    "            nonlocal next_num\n",
    "            next_num = max(num, next_num)\n",
    "            while next_num in exists:\n",
    "                next_num += 1\n",
    "            return next_num\n",
    "\n",
    "        result = 0\n",
    "        for i in range(1, n):\n",
    "            if nums[i] == nums[i-1]:\n",
    "                tmp_next = get_next(nums[i])\n",
    "                # print(i, nums[i], tmp_next)\n",
    "                result += tmp_next - nums[i]\n",
    "                exists.add(tmp_next)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums_set = set()\n",
    "        repeat_arr = list()\n",
    "        for num in nums:\n",
    "            if num in nums_set:\n",
    "                repeat_arr.append(num)\n",
    "            else:\n",
    "                nums_set.add(num)\n",
    "        if len(repeat_arr) == 0:\n",
    "            return  0\n",
    "        repeat_arr.sort()\n",
    "        from_nums = repeat_arr[0]\n",
    "        cur = from_nums\n",
    "        targets = list()\n",
    "        while True:\n",
    "            cur += 1\n",
    "            if cur in nums_set:\n",
    "                continue\n",
    "            else:\n",
    "                targets.append(cur)\n",
    "            if len(targets) >= len(repeat_arr) and targets[-1] > repeat_arr[-1]:\n",
    "                break\n",
    "        result = 0\n",
    "        idx = 0\n",
    "        for r in repeat_arr:\n",
    "            while targets[idx] < r:\n",
    "                idx += 1\n",
    "                if len(targets) == idx:\n",
    "                    a = targets[-1] + 1\n",
    "                    targets.append(a)\n",
    "            result += targets[idx]-r\n",
    "            idx += 1\n",
    "            if len(targets) == idx:\n",
    "                a = targets[-1] + 1\n",
    "                targets.append(a)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        nums.sort()\n",
    "        nums_map = collections.Counter(nums)\n",
    "        idx = 0\n",
    "        keys = list(nums_map.keys())\n",
    "        for key in keys:\n",
    "            idx = max(idx, key + 1)\n",
    "            while nums_map[key] > 1:\n",
    "                while idx in nums_map:\n",
    "                    idx += 1\n",
    "\n",
    "                nums_map[key] -= 1\n",
    "                nums_map[idx] = 1\n",
    "                ans += idx - key\n",
    "                idx += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        count = [0] * 10**6\n",
    "        for x in nums:\n",
    "            count[x] += 1\n",
    "        \n",
    "        ans = taken = 0\n",
    "        for x in range(10**6):\n",
    "            if count[x] >= 2:\n",
    "                taken += count[x] - 1\n",
    "                ans -= x * (count[x] - 1)\n",
    "            elif taken > 0 and count[x] == 0:\n",
    "                taken -= 1\n",
    "                ans += x\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        used = [0]*(10**6)\n",
    "        rest = 0\n",
    "        last_cnt = 0\n",
    "        for num in nums:\n",
    "            used[num]+=1\n",
    "            if used[num]>1:\n",
    "                rest+=num\n",
    "                last_cnt+=1\n",
    "        cur = 0\n",
    "        cnt = 0\n",
    "        i = min(nums)\n",
    "        while last_cnt:\n",
    "            if used[i]==0 and cnt>0:\n",
    "                cnt-=1\n",
    "                last_cnt-=1\n",
    "                cur+=i\n",
    "                i+=1\n",
    "                continue\n",
    "            if used[i]>1:\n",
    "                cnt+=used[i]-1\n",
    "                i+=1\n",
    "                continue\n",
    "            else:\n",
    "                i+=1\n",
    "                continue\n",
    "        return cur-rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        v = set()\n",
    "        nums = [0] + nums\n",
    "        ans = 0\n",
    "        c = []\n",
    "        for i in range(1, len(nums)):\n",
    "            if nums[i] not in v:\n",
    "                v.add(nums[i])\n",
    "            else:\n",
    "                c.append(nums[i])\n",
    "            j = nums[i-1] + 1\n",
    "            while c and j < nums[i]:\n",
    "                ans += j - c.pop()\n",
    "                j += 1\n",
    "        if c:\n",
    "            j = nums[-1] + 1\n",
    "            while c:\n",
    "                ans += j - c.pop()\n",
    "                j += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        set_v = set()\n",
    "        max_v = -inf\n",
    "        cnt = 0\n",
    "        nums.sort()\n",
    "        for v in nums:\n",
    "            if v not in set_v:\n",
    "                set_v.add(v)\n",
    "                max_v = max(max_v, v)\n",
    "            else:\n",
    "                set_v.add(max_v + 1)\n",
    "                cnt += max_v + 1 - v\n",
    "                max_v += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "      n = len(nums)\n",
    "      s = set(nums)\n",
    "      nums.sort()\n",
    "      ans = 0\n",
    "      j = nums[0]\n",
    "      for i in range(1, n):\n",
    "        if nums[i] == nums[i-1]:\n",
    "          j = max(j, nums[i])\n",
    "          while j in s:\n",
    "            j += 1\n",
    "          ans += j - nums[i]\n",
    "          s.add(j)\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        # print(nums)\n",
    "        look_up = set()\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] in look_up:\n",
    "                d =  nums[i - 1] - nums[i] + 1\n",
    "                res += d\n",
    "                nums[i] += d\n",
    "            look_up.add(nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        count=collections.Counter(nums)\n",
    "        #Maximum unique value could have\n",
    "        #e.g. [1,1,10] ->[1,2,10] [10,10,10]->[10,11,12] [14,11,14]->[11,14,15]\n",
    "        max_val = max(nums)+len(nums) \n",
    "        repeat = []\n",
    "        # res = []\n",
    "        move = 0\n",
    "        #iterate over all possible values the array can take\n",
    "        #if count==1 -> continue\n",
    "        #if count>=2 -> add repeated items into repear\n",
    "        #if count==0, pop a repeated items and change it to the current num\n",
    "        for i in range(max_val):\n",
    "            if count[i]>=2:\n",
    "                #extend - append the list into another list\n",
    "                repeat.extend([i]*(count[i]-1))\n",
    "            elif repeat and count[i]==0:\n",
    "                cur = repeat.pop()#pop the last item in repeat\n",
    "                move += i-cur\n",
    "                # res.append(cur)\n",
    "            # elif count[i]==1:\n",
    "            #     res.append(i)\n",
    "        return move\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        if len(set(nums))==len(nums):\n",
    "            return 0\n",
    "        else:\n",
    "            nums=sorted(nums)\n",
    "            k=0\n",
    "            for i in range(1,len(nums)):\n",
    "                if nums[i]<=nums[i-1]:\n",
    "                    k+=nums[i-1]-nums[i]+1\n",
    "                    nums[i]=nums[i-1]+1\n",
    "            return k "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        min_val = nums[0]\n",
    "        his = set(nums)\n",
    "        copy_nums = nums[:]\n",
    "        ans = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            if copy_nums[i] == copy_nums[i-1]:\n",
    "                nums[i] = min_val + 1\n",
    "                while nums[i] in his:\n",
    "                    nums[i] += 1\n",
    "                min_val = nums[i]\n",
    "                his.add(min_val)\n",
    "                ans += (min_val - copy_nums[i])\n",
    "            else:\n",
    "                min_val = max(nums[i], min_val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        if len(nums) <= 1:\n",
    "            return 0\n",
    "        \n",
    "        if len(nums) == 2:\n",
    "            return 0 if nums[0] != nums[1] else 1\n",
    "        \n",
    "        d = defaultdict(int)\n",
    "        for num in nums:\n",
    "            d[num] += 1\n",
    "\n",
    "        max_num = max(nums)\n",
    "        ans = 0\n",
    "        arr = [[k,v] for k, v in d.items() if v > 1]\n",
    "        if len(arr) == 0:\n",
    "            return 0\n",
    "        \n",
    "        arr.sort()\n",
    "        min_num = arr[0][0]\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(min_num+1, max_num):\n",
    "            if len(arr) > 0:\n",
    "                num, times = arr[0]\n",
    "                if i not in d and i > num:\n",
    "                    ans += i-num\n",
    "                    times -=1\n",
    "                    if times == 1:\n",
    "                        arr.pop(0)\n",
    "                    else:\n",
    "                        arr[0][1] = times\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        i = max_num + 1\n",
    "        while len(arr) > 0:\n",
    "            num, times = arr[0]\n",
    "            ans += (i-num)\n",
    "            times -= 1\n",
    "            if times == 1:\n",
    "                arr.pop(0)\n",
    "            else:\n",
    "                arr[0][1] -= 1\n",
    "            i += 1\n",
    "\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        num_ts = {}\n",
    "        for num in nums:\n",
    "            num_ts[num] = num_ts.get(num, 0) + 1\n",
    "        nums = sorted(list(num_ts.keys()))\n",
    "        res = 0\n",
    "        # cur = -1\n",
    "        # i = 0\n",
    "        # while cur != -1 or i < len(nums):\n",
    "        #     if cur == -1:\n",
    "        #         res += num_ts[nums[i]]-1\n",
    "        #         if num_ts[nums[i]] > 1:\n",
    "        #             num_ts[nums[i]+1] = num_ts.get(nums[i]+1, 0) + num_ts[nums[i]]-1\n",
    "        #             cur = nums[i]+1\n",
    "        #         i += 1\n",
    "        #     else:\n",
    "        #         res += num_ts[cur]-1\n",
    "        #         if i < len(nums)  and cur == nums[i]:\n",
    "        #             i += 1\n",
    "        #         if num_ts[cur] > 1:\n",
    "        #             num_ts[cur+1] = num_ts.get(cur+1, 0) + num_ts[cur]-1\n",
    "        #             cur = cur+1\n",
    "        #         else:\n",
    "        #             cur = -1\n",
    "        \n",
    "        cur = nums[0]\n",
    "        for num in nums:\n",
    "            while num_ts[num] != 1:\n",
    "                if cur<num:\n",
    "                    cur = num\n",
    "                while cur in num_ts:\n",
    "                    cur += 1\n",
    "                num_ts[cur] = 1\n",
    "                # print(num, cur, num_ts)\n",
    "                res += cur-num\n",
    "                num_ts[num] -= 1\n",
    "        return res  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        mx = max(nums)\n",
    "        ans = 0\n",
    "        for i in range(mx + 1):\n",
    "            if cnt[i] > 0:\n",
    "                d = cnt[i] - 1 # 有d个数需要增大一位\n",
    "                ans += d\n",
    "                cnt[i + 1] += d\n",
    "        \n",
    "        \"\"\"\n",
    "        cnt[mx + 1]可能有多个从mx转移过来的，留下一个，其余d个往后挪\n",
    "        设 mx + 1 = x, 那么后面的d个数就是[x+1, x+2,...,x+d]\n",
    "        因此操作数为[1,2,..,d]\n",
    "        \"\"\"\n",
    "        d = cnt[mx + 1] - 1\n",
    "        ans += (1 + d) * d // 2\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        book = Counter(nums)\n",
    "        y = nums[0]\n",
    "        for x, y in pairwise(sorted(book)):\n",
    "            if (fx := book[x]) > 1:\n",
    "                diff = fx if fx < y - x else y - x\n",
    "                fx -= diff\n",
    "                book[y] += fx\n",
    "                ans += ((diff * (diff - 1)) >> 1) + (fx * (y - x))\n",
    "        g = book[y] - 1\n",
    "        return ans + ((g * (g + 1)) >> 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\"\"\" \n",
    "    2023-10-06\n",
    "    [4 4 5 5 5] --> [4 8(+4) 5 6(+1) 7(+2)], 移动次数为 7\n",
    "    [4 4 5 5 5] --> [4 5(+1) 6(+1) 7(+2) 8(+3)] 移动次数为 7\n",
    "\n",
    "    给定 [3 2 1 2 1 7],\n",
    "    step1: 排序 --> [1 1 2 2 3 7]\n",
    "    step2: 从左至右遍历\n",
    "        1 --> 1 (+0)   【cur_avaiable = 2, 表示如果下一个值 num 是重复值，应该将其移动到 cur_available】\n",
    "        1 --> 2 (+1)   【1 in visited, 移动 1 到 cur_avaiable=2, visited.add(2)，cur_available=2+1=3】\n",
    "        2 --> 3 (+1)   【2 in visited，移动到 cur_available=3, visited.add(3),cur_available=3+1=4】\n",
    "        2 --> 4 (+2)   【2 in visited，2 --> cur_available=4, visited.add(4), cur_available=4+1=5】\n",
    "        3 --> 5 (+2)   【3 in visited, 3 --> cur_available=5, visited.add(5), cur_available=5+1=6】\n",
    "        7 --> 7 (+0)   【7 not in visited, 不进行移动，visited.add(7), cur_available=7+1=8】\n",
    "        总共变化 6 次\n",
    "\n",
    "    维护一个 visited 集合，表示已经使用过的数字，在遍历 num 时，如果 num in visted, 则需要移动 num 到 cur_available, 并且添加到集合 visited.add(num), 下一个可以占用的值为 num + 1. \n",
    "    \n",
    "\n",
    " \"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums = sorted(nums)\n",
    "        visited = set()\n",
    "        visited.add(nums[0])\n",
    "        cur_available = nums[0] + 1  ## 当前可用的值\n",
    "        count = 0\n",
    "        for num in nums[1:]:\n",
    "            if num in visited:\n",
    "                count += cur_available - num \n",
    "                num  = cur_available\n",
    "                visited.add(cur_available)  \n",
    "            else:\n",
    "                visited.add(num)\n",
    "            cur_available = num + 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        dic={ j :0 for j in nums}\n",
    "        for j in nums:\n",
    "            dic[j]+= 1 \n",
    "        l= sorted( dic.keys( ) ) \n",
    "        print( dic )\n",
    "        ans = 0\n",
    "        for j in range( len( l) -1 ) :\n",
    "            if (  dic [  l[j] ] <= (  l[j+1] - l[j ]  )     ) :\n",
    "                n = dic[ l[j] ]  \n",
    "                ans +=  ( n-1)*n//2 \n",
    "            else:\n",
    "                dic[ l[j+1]] +=  (  dic [  l[j] ] - ( l[j+1] - l[j ]  )) \n",
    "                n= l[j+1] - l[j ] \n",
    "                ans +=  ( n-1)*n//2  \n",
    "                ans +=   ( l[j+1] - l[j ] )*(  dic [  l[j] ] - ( l[j+1] - l[j ]  )) \n",
    "        n=dic[ l[-1]]\n",
    "        ans +=  ( n-1)*n//2\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        book = defaultdict(int)\n",
    "        for num in nums: book[num] += 1\n",
    "        y = nums[0]\n",
    "        for x, y in pairwise(sorted(book)):\n",
    "            if (fx := book[x]) > 1:\n",
    "                diff = fx if fx < y - x else y - x\n",
    "                fx -= diff\n",
    "                book[y] += fx\n",
    "                ans += ((diff * (diff - 1)) // 2) + (fx * (y - x))\n",
    "        g = book[y] - 1\n",
    "        return ans + ((g * (g + 1)) // 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        pos = min(nums)\n",
    "        d = dict()\n",
    "        for num in nums:\n",
    "            if num not in d:\n",
    "                d[num] = 1\n",
    "            else:\n",
    "                d[num] += 1\n",
    "        dup = []\n",
    "        res = 0\n",
    "        while True:\n",
    "            if d.get(pos, 0) > 1:\n",
    "                dup.append(pos)\n",
    "            if dup and pos not in d:\n",
    "                a = dup[-1]\n",
    "                d[a] -= 1\n",
    "                if d[a] == 1:\n",
    "                    dup.pop()\n",
    "                d[pos] = 1\n",
    "                res += pos - a\n",
    "            if len(d) == len(nums):\n",
    "                break\n",
    "            pos += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        counter = collections.Counter(sorted(nums))\n",
    "        cur = 0\n",
    "        for i in list(counter.keys()):\n",
    "            while counter[i] > 1:\n",
    "                cur = max(cur,i+1)\n",
    "                while counter[cur] != 0:\n",
    "                    cur+=1\n",
    "                counter[i]-=1\n",
    "                counter[cur] += 1\n",
    "        return sum(counter.keys())- sum(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import *\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        s=set()\n",
    "        no_rep=[]\n",
    "        rep=[]\n",
    "        max_num=-inf\n",
    "        for num in nums:\n",
    "            if num not in s:\n",
    "                s.add(num)\n",
    "                no_rep.append(num)\n",
    "            else:\n",
    "                rep.append(num)\n",
    "        heapify(no_rep)\n",
    "        heapify(rep)\n",
    "        cnt=0\n",
    "        while rep:\n",
    "            t=heappop(rep)\n",
    "            while no_rep:\n",
    "                x1=heappop(no_rep)\n",
    "                x2=no_rep[0] if len(no_rep)>0 else inf\n",
    "                if x1<t or x2-x1<=1:\n",
    "                    continue\n",
    "                heappush(no_rep,x1+1)\n",
    "                cnt+=(x1+1-t)\n",
    "                break\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        d=dict()\n",
    "        s=set()\n",
    "        ans=0\n",
    "        for n in nums:\n",
    "            if n not in s:\n",
    "                s.add(n)\n",
    "            else:\n",
    "                last=n\n",
    "                while n in s:\n",
    "                    if n in d:\n",
    "                        n=d[n]\n",
    "                    else:\n",
    "                        n=n+1\n",
    "                s.add(n)\n",
    "                ans+=n-last\n",
    "                d[last]=n+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        a = set(nums)\n",
    "        visited = set()\n",
    "        i, j = 0, 0\n",
    "        res = 0\n",
    "        while(i < n):\n",
    "            if nums[i] not in visited:\n",
    "                visited.add(nums[i])\n",
    "                i += 1\n",
    "                continue\n",
    "            if nums[i] > j:\n",
    "                j = nums[i] \n",
    "            while(j in a):\n",
    "                j += 1 \n",
    "            res += j-nums[i]\n",
    "            j += 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        print(10e5)\n",
    "        counter = [0] * int(10e5 + 1)\n",
    "        maxNum = -1\n",
    "        for num in nums:\n",
    "            counter[num] += 1\n",
    "            maxNum = max(maxNum, num)\n",
    "\n",
    "        move = 0\n",
    "        for i in range(maxNum + 1):\n",
    "            if counter[i] > 1:\n",
    "                d = counter[i] - 1\n",
    "                move += d\n",
    "                counter[i + 1] += d\n",
    "\n",
    "        d = counter[maxNum + 1] - 1\n",
    "        move += (1 + d) * d // 2\n",
    "        return move\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "#         nums = sorted(nums)\n",
    "#         move = 0\n",
    "#         for i in range(1, len(nums)):\n",
    "#             # // 遍历数组，若当前元素小于等于它的前一个元素，则将其变为前一个数+1\n",
    "#             if nums[i - 1] >= nums[i]:\n",
    "#                 pre = nums[i]\n",
    "#                 nums[i] = nums[i - 1] + 1\n",
    "#                 move += nums[i] - pre\n",
    "#         return move\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        a = set(nums)\n",
    "        visited = set()\n",
    "        i, j = 0, 0\n",
    "        res = 0\n",
    "        while(i < n):\n",
    "            if nums[i] not in visited:\n",
    "                visited.add(nums[i])\n",
    "                i += 1\n",
    "                continue\n",
    "            j = max(j, nums[i])\n",
    "            while(j in a):\n",
    "                j += 1 \n",
    "            res += j-nums[i]\n",
    "            j += 1\n",
    "            i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        taken = []\n",
    "        freq = collections.Counter(nums)\n",
    "\n",
    "        ret = 0\n",
    "        for i in range(len(nums)+max(nums)):\n",
    "            if freq[i] >= 2:\n",
    "                taken.extend([i]*(freq[i]-1))\n",
    "            elif freq[i] == 0:\n",
    "                if taken:\n",
    "                    ret += i - taken.pop()\n",
    "        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        ndict = Counter(nums)\n",
    "        unique_n = list(ndict.keys())\n",
    "        ans = 0\n",
    "        maxtaken = unique_n[0] - 1\n",
    "        for i, k in enumerate(unique_n):\n",
    "            if i == 0:\n",
    "                stp = 1\n",
    "            elif i > 0 and maxtaken <= k:\n",
    "                stp = 1\n",
    "            elif i == len(unique_n)-1:\n",
    "                if maxtaken <= k:\n",
    "                    stp = 1\n",
    "                else:\n",
    "                    stp = maxtaken -k + 1\n",
    "            else:\n",
    "                stp = maxtaken - k + 1\n",
    "            while ndict[k] > 1:\n",
    "                if ndict.get(k+stp):\n",
    "                    stp += 1\n",
    "                else:\n",
    "                    ndict[k+stp] = 1\n",
    "                    maxtaken = k+stp\n",
    "                    ndict[k] -= 1\n",
    "                    ans += stp\n",
    "                    stp += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        count = [0] * 1000001\n",
    "        for x in nums:\n",
    "            count[x] += 1\n",
    "        \n",
    "        ans = taken = 0\n",
    "        for x in range(1000001):\n",
    "            if count[x] >= 2:\n",
    "                taken += count[x] - 1\n",
    "                ans -= x * (count[x] - 1)\n",
    "            elif taken > 0 and count[x] == 0:\n",
    "                taken -= 1\n",
    "                ans += x\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        count = [0] * 1000000\n",
    "        for x in nums:\n",
    "            count[x] += 1\n",
    "        ans = taken = 0\n",
    "        for x in range(1000000):\n",
    "            if count[x] >= 2:\n",
    "                taken += count[x] - 1\n",
    "                ans -= x * (count[x] - 1)\n",
    "            elif taken >0 and count[x] == 0:\n",
    "                taken -= 1\n",
    "                ans += x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        cnt = {}\n",
    "        res = 0\n",
    "        nums = sorted(nums)\n",
    "        st = nums[0]\n",
    "        for v in nums:\n",
    "            while v in cnt:\n",
    "                if v + 1 < st:\n",
    "                    res += st - v\n",
    "                    v = st\n",
    "                else:\n",
    "                    v += 1\n",
    "                    res += 1\n",
    "            cnt[v] = 1\n",
    "            st = v + 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, A: List[int]) -> int:\n",
    "        # one=[]\n",
    "        # for i in range(len(A)): \n",
    "        #     if A[i] not in one:\n",
    "        #         one.append(A[i])\n",
    "        #     else:\n",
    "        #         k=A[i]+1\n",
    "        #         while k in one:\n",
    "        #             k+=1\n",
    "        #         one.append(k)\n",
    "\n",
    "        # 排序法\n",
    "        # move=0\n",
    "        # A.sort() \n",
    "        # for index in range(1,len(A)):\n",
    "        #     if A[index]<=A[index-1]:\n",
    "        #         move+=A[index-1]+1-A[index]\n",
    "        #         A[index]=A[index-1]+1\n",
    "        # return move\n",
    "\n",
    "        # 计数法\n",
    "        # counter=[0]*80001\n",
    "        # max_num=0\n",
    "        # move=0\n",
    "        # for num in A:\n",
    "        #     counter[num]+=1\n",
    "        #     max_num=max(max_num,num)\n",
    "        # for i in range(0,max_num+1):\n",
    "        #     if counter[i]>1:\n",
    "        #         counter[i+1]+=counter[i]-1\n",
    "        #         move+=counter[i]-1\n",
    "        # last=counter[max_num+1]-1\n",
    "        # move+=int(last*(last+1)/2)\n",
    "        # return move\n",
    "\n",
    "        # 线性探测\n",
    "        def findpos(a):\n",
    "            b=pos[a]\n",
    "            if b==-1:\n",
    "                pos[a]=a\n",
    "                return a\n",
    "            b=findpos(b+1)\n",
    "            pos[a]=b\n",
    "            return b\n",
    "\n",
    "        move=0\n",
    "        pos=[-1]*80000\n",
    "        for a in A:\n",
    "            b=findpos(a)\n",
    "            move+=b-a\n",
    "        return move\n",
    "\n",
    "       \n",
    "            \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        cnt = Counter(nums)\n",
    "        mx = max(cnt)\n",
    "        move = 0\n",
    "        for i in range(mx+1):\n",
    "            if cnt[i] > 1:\n",
    "                d = cnt[i]-1\n",
    "                cnt[i] = 1\n",
    "                move += d\n",
    "                cnt[i+1] += d\n",
    "        d = cnt[mx+1]-1\n",
    "        move += d*(d+1)//2\n",
    "        return move\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minIncrementForUnique(self, nums: List[int]) -> int:\n",
    "        c = Counter(nums)\n",
    "        mn = min(nums)\n",
    "        mx = max(nums)+ len(nums)\n",
    "        ans = 0\n",
    "        for i in range(mn,mx):\n",
    "            if c[i]>1:\n",
    "                ans += c[i] - 1\n",
    "                c[i+1] += c[i] - 1\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
